package com.zjsru.plan2025.oneday;

import java.util.HashMap;
import java.util.Map;

/**
 * 781. 森林中的兔子
 *
 * @Author: cookLee
 * @Date: 2025-04-20
 */
public class NumRabbits {

    /**
     * 主
     * \
     * 输入：answers = [1,1,2]
     * 输出：5
     * 解释：
     * 两只回答了 "1" 的兔子可能有相同的颜色，设为红色。
     * 之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
     * 设回答了 "2" 的兔子为蓝色。
     * 此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
     * 因此森林中兔子的最少数量是 5 只：3 只回答的和 2 只没有回答的。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        NumRabbits numRabbits = new NumRabbits();
        int[] answers = {1, 1, 2};
        System.out.println(numRabbits.numRabbits(answers));
    }

    public int numRabbits(int[] answers) {
        int ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int answer : answers) {
            map.put(answer, map.getOrDefault(answer, 0) + 1);
        }
        //如果有 x 只兔子都回答 y，则至少有 x/y+1 种颜色的兔子，同时 （x/y+1）（y+1）的兔子
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            //key：表示当前回答值，即某只兔子声称与它相同颜色的兔子数量为 key。
            int key = entry.getKey();
            //value：表示回答值为 key 的兔子数量。
            int value = entry.getValue();
            //(value + key) / (key + 1)：计算需要多少组兔子来容纳所有回答值为 key 的兔子。以及总数
            ans += (value + key) / (key + 1) * (key + 1);
        }
        return ans;
    }

}
